package com.xy6.struct.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树
 * 
 * @author zhang
 * @since 2017-09-17
 *
 * @param <T>
 */
public class BinaryTree<T> {

	private BinaryTreeNode<T> root;
	
	public BinaryTree(){
	}
	
	public BinaryTree(BinaryTreeNode<T> root){
		this.root = root;
	}

	public BinaryTreeNode<T> getRoot() {
		return root;
	}

	public void setRoot(BinaryTreeNode<T> root) {
		this.root = root;
	}
	
	/**
	 * 根据值查找节点
	 * <pre>
	 * 时间复杂度：O(n)
	 * </pre>
	 * 
	 * @param data
	 * @return
	 */
	public BinaryTreeNode<T> search(T data){
		return searchTree(getRoot(), data);
	}
	
	/**
	 * 根据值查找节点
	 * <pre>
	 * 时间复杂度：O(n)
	 * </pre>
	 * 
	 * @param data
	 * @return
	 */
	public BinaryTreeNode<T> search(BinaryTreeNode<T> node, T data){
		return searchTree(node, data);
	}
	
	/**
	 * 添加左子节点
	 * 
	 * @param manyTreeNode
	 * @param child
	 */
	public void addLeftChild(BinaryTreeNode<T> parent, BinaryTreeNode<T> child) {
		parent.setLeft(child);
	}
	
	/**
	 * 添加右子节点
	 * 
	 * @param manyTreeNode
	 * @param child
	 */
	public void addRightChild(BinaryTreeNode<T> parent, BinaryTreeNode<T> child) {
		parent.setRight(child);
	}
	
	/**
	 * 获取所有节点集合
	 * <pre>
	 * 时间复杂度：O(n)
	 * </pre>
	 * 
	 * @return
	 */
	public List<BinaryTreeNode<T>> getNodes() {
		return iteror(this.root);
	}
	
	/**
	 * 从根节点开始，遍历一棵子树
	 * <p>深度优先算法
	 * 
	 * @param node
	 * @return
	 */
	private List<BinaryTreeNode<T>> iteror(BinaryTreeNode<T> node) {
		if (null == node) {
			return null;
		}
		List<BinaryTreeNode<T>> nodes = new ArrayList<>();
		nodes.add(node);
		if(null == node.getChildList() || node.getChildList().isEmpty()){
			return nodes;
		}
		for (BinaryTreeNode<T> index : node.getChildList()) {
			List<BinaryTreeNode<T>> temp = iteror(index);
			if (temp != null) {
				nodes.addAll(temp);
			}
		}
		return nodes;
	}
	
	/**
	 * 查找值为data的节点
	 * 
	 * @param node
	 * @param data
	 * @return
	 */
	private BinaryTreeNode<T> searchTree(BinaryTreeNode<T> node, T data) {
		if (null == node) {
			return null;
		}
		if(node.getData().equals(data)){
			return node;
		}
		if(null == node.getChildList() || node.getChildList().isEmpty()){
			return null;
		}
		for (BinaryTreeNode<T> index : node.getChildList()) {
			BinaryTreeNode<T> temp = search(index, data);
			if (temp != null) {
				return temp;
			}
		}
		return null;
	}
	
	/**
	 * 删除一个节点
	 * <pre>
	 * 1 节点为叶子节点
	 * 2 节点只有一个子节点
	 * 3 节点有两个子节点
	 * </pre>
	 * 
	 * @param node
	 * @return
	 */
	public boolean remove(BinaryTreeNode<T> node){
		// 空树
		if(null == root){
			return false;
		}
		// 为叶子节点
		if(null == node.getLeft() && null == node.getRight()){
			// 根节点
			if(null == node.getParent()){
				root = null;
				return true;
			}
			if(node.getParent().getLeft() == node){
				node.getParent().setLeft(null);
			} else if(node.getParent().getRight() == node){
				node.getParent().setRight(null);
			}
			return true;
		}
		
		// 只有一个子节点
		if(null == node.getLeft() || null == node.getRight()){
			// 只有左子节点
			if(null != node.getLeft()){
				// 根节点
				if(null == node.getParent()){
					root = node.getLeft();
					root.setParent(null);
					node.setLeft(null);
					return true;
				}
				if(node.getParent().getLeft() == node){
					node.getParent().setLeft(node.getLeft());
					node.getLeft().setParent(node.getParent());
					node.setParent(null);
					node.setLeft(null);
				} else if(node.getParent().getRight() == node){
					node.getParent().setRight(node.getLeft());
					node.getLeft().setParent(node.getParent());
					node.setParent(null);
					node.setLeft(null);
				}
				return true;
			}
			// 只有右子节点
			if(null == node.getParent()){
				root = node.getRight();
				root.setParent(null);
				node.setRight(null);
				return true;
			}
			if(node.getParent().getLeft() == node){
				node.getParent().setLeft(node.getRight());
				node.getRight().setParent(node.getParent());
				node.setParent(null);
				node.setRight(null);
			} else if(node.getParent().getRight() == node){
				node.getParent().setRight(node.getRight());
				node.getRight().setParent(node.getParent());
				node.setParent(null);
				node.setRight(null);
			}
			return true;
		}
		
		// 有两个子节点
		update(node);
		
		return false;
	}
	
	/**
	 * 将当前节点的一个子节点向上提一个层级
	 * 
	 * TODO 待优化
	 * 
	 * <pre>
	 * node的子节点a1，向上移动
	 * a1的子节点b1，向上移动
	 * b1的子节点c1，向上移动
	 * 递归向下遍历，直至叶子节点
	 * 
	 * 时间复杂度：O(height)
	 * </pre>
	 * 
	 * @param node
	 */
	private void update(BinaryTreeNode<T> node){
		List<BinaryTreeNode<T>> nodes = new ArrayList<>();
		// nodes至少有2个元素
		getReplaceNodes(node, nodes);
		// 第1个节点需要被替换，后续节点不需要
		BinaryTreeNode<T> first = nodes.get(0);
		BinaryTreeNode<T> elem = nodes.get(1);
		BinaryTreeNode<T> right = elem.getRight();
		elem.setParent(first.getParent());
		elem.setRight(first.getRight());
		
		if(null == node.getParent()){
			// 根节点
			this.root = elem;
		} else if(node.getParent().getLeft() == node){
			node.getParent().setLeft(elem);
		} else {
			node.getParent().setRight(elem);
		}
		first.setParent(null);
		first.setLeft(null);
		first.setRight(null);
		if(nodes.size() > 2){
			elem.setLeft(nodes.get(2));
		} else {
			return;
		}
		
		// 第2个节点只有一个子节点
		if(null == elem.getLeft() || null == right){
			return;
		}
		
		BinaryTreeNode<T> rightPreNode = right;
		BinaryTreeNode<T> rightCurNode;
		for (int i = 2; i < nodes.size(); i++) {
			nodes.get(i-1).setLeft(nodes.get(i));
			// 父节点只有一个右子节点
			if(rightPreNode == nodes.get(i)){
				break;
			}
			rightCurNode = nodes.get(i).getRight();
			nodes.get(i).setRight(rightPreNode);
			rightPreNode = rightCurNode;
			// 只有一个左子节点
			if(null == rightCurNode){
				break;
			}
		}
	}
	
	/**
	 * 获取一个节点待替换的所有子节点
	 * <pre>
	 * 时间复杂度：O(height)
	 * </pre>
	 * 
	 * @param node
	 * @param road
	 */
	private void getReplaceNodes(BinaryTreeNode<T> node, List<BinaryTreeNode<T>> road){
		if(null == node){
			return;
		}
		road.add(node);
		if(null != node.getLeft()){
			getReplaceNodes(node.getLeft(), road);
		} else if(null != node.getRight()){
			getReplaceNodes(node.getRight(), road);
		}
	}
	
	/**
	 * 删除一个节点及其子节点
	 * 
	 * @param node
	 * @return
	 */
	public boolean removeCascade(BinaryTreeNode<T> node){
		if(null == node){
			return false;
		}
		// 根节点
		if(null == node.getParent()){
			root = null;
			return true;
		}
		if(node.getParent().getLeft() == node){
			node.getParent().setLeft(null);
		} else if(node.getParent().getRight() == node){
			node.getParent().setRight(null);
		}
		node.setParent(null);
		
		return true;
	}
	
}
